package solvers.linearsupport;

import globals.CentralStatics;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

import value.LazyScalarizedVector;
import value.ValueAtBeliefVector;

public class LinearSupporter<T> implements ValueCollection<T>{
	/*
	 * Author: Diederik M. Roijers, University of Amsterdam
	 * 
	 * This class contains the code for Optimistic Linear Support; an abstract
	 * algorithm for multi-objective optimization in decision problems. 
	 * 
	 * The algorithm is parameterized with four variables, in the constructor:
	 * 1) SingleSolver<T> sw :: a interface containing a function "public Payoff<T> 
	 * 		solveForW(double[] w)" that solves a linearly scalarized version of
	 * 		a decision problem and returns the multiobjective value of the optimum
	 * 		tagged (type T) with the underlying decision. 
	 * 2) double precisionE :: a parameter to avoid rounding errors, usually picked 
	 * 		best around a factor 100 smaller than the next parameter (stopCrit)
	 * 3) double stopCrit :: an epsilon value: OLS will return an epsilon-CCS
	 * 		if an exact solution is required, this parameter should be "0"
	 * 4) int dimensions :: the number of objectives in the decision problem.
	 * 
	 * The main function in this class is: 
	 * 		ArrayList<Payoff<T>> runLinearSupport(long maxTime)
	 * which runs OLS with a timeOut set at maxTime, and returns the epsilon-CCS as
	 * an ArrayList. 
	 * 
	 * Two important classes that are not necessarily in the algorithm but are referred
	 * to in this class are: 
	 * 1) the interface SingleSolver, an instance of which is required
	 * 2) Payoff<T>, from the payoffs package that models the vector-valued utility and
	 * 		can be "public void tag(T t)"'ed with a/many (partial) solutions. 
	 */

	public SingleSolver<T> solverW; //the function that can solve scalarized instances
	public double precision, epsilon; 
	public ArrayList<ValueVector<T>> vvs; //Containing the optimal vector valued utilities in the (epsilon-)CCS
	public PriorityQueue<CornerPoint<T>> cps; //Containing the corner weights, 
					// contained in the vertices of the 
					// polyhedron spanned by the value vectors in R^(dim+1) (augmented with the scalarized value)
					// above the weight simplex. 
	public int dim; //the number of objectives
	public boolean prioritized;//deprecated: turning this off will lead to an inefficient algorithm
	public final static boolean optimize2D=true; //Do use when solving two objective problems, it turns off
					//several checks which are not necessary in 2D (i.e., it saves time)
	public final static int[] standardSWI2D = {0,0};//used in the 2D optimized version of OLS.
	public final static boolean[] standardW02D = {false,false};//used in the 2D optimized version of OLS.
	
	public long readoutTime;//a field containing the total runtime of OLS when finished. 
	
	public final static boolean DEBUG=false;//Will turn on a lot of output to the System.out 
	
	public ArrayList<ValueAtBeliefVector<T>> listmaxlnsupp=new ArrayList<ValueAtBeliefVector<T>>();
	
	public LinearSupporter(SingleSolver<T> sw, double precisionE, double stopCrit, int dimensions){
		solverW = sw;
		precision = precisionE; 
		epsilon = stopCrit;
		vvs = new ArrayList<ValueVector<T>>();
		dim = dimensions;
		cps = new PriorityQueue<CornerPoint<T>>();
		this.prioritized=true;
		//this.init(); //MOVED to runLinearSupport in order to be able to meaure the runtime.
		readoutTime=0;
	}
	
	public void init(){
		//Running the extrema of the weight simplex to the priority queue of 
		//the corner weights, as the first corner weights to check,
		//(infinite priority, because the maximal utility in the individual 
		// objectives are still unknown until these extrema have been checked).
		vvs = new ArrayList<ValueVector<T>>();
		Comparator<CornerPoint<T>> comparator = new CPComparator<T>();
		this.cps = new PriorityQueue<CornerPoint<T>>(10,comparator);
		double[] w = new double[dim];
		double[] maxVals = new double[dim];
		for(int i=0; i<dim; i++){w[i]=0.0; maxVals[i]=0;}
		
		for(int i=0; i<dim; i++){
		      //For each extremum
			  if(i>0){w[i-1]=0;}
		      w[i]=1;
		     
		      //Find the maximizing value vector...
		      ValueVector<T> vv = new ValueVector<T>( solverW.solveForW(w), w.clone());
		      //System.out.println(vv.p.retrieveTags());
		      System.out.println("checking");
		      maxVals[i]=vv.valueAtSearchWeights[0];
		      boolean found=false;
		    
		      //... check whether this one was already in the CCS ...
		      for(int j=0; j<vvs.size(); j++){
		    	 ValueVector<T> va = vvs.get(j);
		         if(vv.p.equalValues(va.p)){
		            va.addSearchWeight(w);
		            found=true;
		            break;
		         }
		      }
		      if(!found){
		    	  //...and if not, add it to the partial CCS
		          vvs.add(vv);
			     

		      }
		}
		if(DEBUG){
			System.out.println("#ValueVectors@init: "+vvs.size());
			for(ValueVector<T> vv : this.vvs){
				System.out.println(vv.toString());
			}
		}
		
		boolean[] combo = new boolean[vvs.size()];
		for(int i=0; i<vvs.size();i++){combo[i]=false;}
		
		boolean done=false;
		//Then, find the corner weights to initialize the priority queue
		// of corner weights to check with. 
		while(!done){
			//only if there are at least two vectors available in the combo:
			if(comboAccept(combo)){
				//boolean[] zeroWeights = new boolean[dim];
				//for(int i=0; i<dim;i++){zeroWeights[i]=false;}
				ArrayList<ValueVector<T>> combs = new ArrayList<ValueVector<T>>();
				for(int i=0; i<combo.length; i++){
					if(combo[i]){
						combs.add(vvs.get(i));
					}
				}
				this.cps.addAll(this.recursiveObtainCornerPoints(null, combs, null, 0, maxVals));
			}
			
			//And, increase the combinator:
			int inc=0; 
			while(inc<vvs.size()){
				if(!combo[inc]){
					combo[inc]=true;
					inc = vvs.size()+1;
				} else {
					combo[inc] = false;
					inc++;
					if(inc>=vvs.size()){
						done = true;
					}
				}
			}
		}
		if(DEBUG){
			System.out.println("#CornerPoints@init: "+this.cps.size());
			for(CornerPoint<T> cp : this.cps){
				System.out.println(cp.toString());
			}
		}
		
		
	}
	
	private boolean comboAccept(boolean[] combo){
	   boolean found1=false;
	   for(int i=0; i<combo.length; i++){
	      if(combo[i]){
	         if(found1){
	            return true;
	         } else {
	            found1=true;
	         }
	      }
	   }
	   return false;
	}
	
	private boolean comboAccept(boolean[] combo, int x){
	   if(x==0&&combo.length==0){return true;}
	   int cnt=0;
	   for(int i=0; i<combo.length; i++){
	      if(combo[i]){
	         cnt++;
	      }
	   }
	   return x==cnt;
	}
	
	private int comboCount(boolean[] combo){
	   int cnt=0;
	   for(int i=0; i<combo.length; i++){
	      if(combo[i]){
	         cnt++;
	      }
	   }
	   return cnt;
	}

	public boolean alreadyContained(ValueVector<T> vv){
		for(int i=0; i<this.vvs.size(); i++){
			if(vv.equals(vvs.get(i))){
				return true;
			}
		}
		return false;
	}
	
	public boolean alreadyContained(ValueAtBeliefVector<T> py){
		for(int i=0; i<this.vvs.size(); i++){
			if(vvs.get(i).equals(py)){
				return true;
			}
		}
		return false;
	}
	
	public ArrayList<ValueVector<T>> getValueVectors(){
		return this.vvs;
	}
	
	//running OLS, finding the (epsilon-)CCS. 
	//maxTime is a time-out limit.
	public ArrayList<ValueAtBeliefVector<T>> runLinearSupport(long maxTime){
		long startTime = System.currentTimeMillis();
		
		this.init();
		
		//System.out.println("init");
		boolean timeout = maxTime < (System.currentTimeMillis()-startTime);
		
		//////////////////////////////////////
		////Main Loop of Algorithm
		/////////////////////////////////////
		//vvs.remove(0);
		//vvs.remove(0);
		while(!this.cps.isEmpty() && !timeout){
		
			//System.out.println("VV SIZE @ LinSup: "+this.vvs.size());
			if(DEBUG){
				System.out.println(">> runLS: "+cps.size()+" cornerPoints " + (System.currentTimeMillis()-startTime) + "ms/"+maxTime+"ms spent.");
			}
			
			CornerPoint<T> currentW = cps.remove();
			
			if(DEBUG){System.out.println(">> for cp: \n"+currentW.toString());}
			ValueAtBeliefVector<T> p = solverW.solveForW(currentW);
			////////////////////////////////////////
			/////checking value at belief
			//System.out.println("checking value at belief    weights :"+p.weight[0]+" "+p.weight[1]);
			//System.out.println("checking value at belief    tag :"+p.retrieveTags().get(0));
			//System.out.println("checking value at belief    valuevec:"+p.getValue()[0]+" "+p.getValue()[1]);
			//Double valvb=p.linearScalValue(p.weight);
			//if(p.retrieveTags().get(0)!=null)
			//{
			
			//**************************************************************************************
			listmaxlnsupp.add(p); 
			//**************************************************************************************
			//}
			
			
			if(!this.alreadyContained(p)){
				if(DEBUG){
					System.out.println(">> Found Payoff: \n"+p.toString());
					//System.out.println(">> for cp: \n"+currentW.toString());
				}
				ValueVector<T> nvv = new ValueVector<T>(p, currentW.weightVector);
				if(!Double.isNaN(nvv.valueAtSearchWeights[0]) &&
						(nvv.valueAtSearchWeights[0]-currentW.value > this.precision) ){
					this.vvs.add(nvv);
					
					////checking
					//listmaxlnsupp.add(p);
					
					if(optimize2D && this.dim==2){
						//For 2D a corner weight always involves two value vectors, because the boundries
						//of the weight simplex are already checked in init:
						ValueVector<T> vec1 = currentW.valueVectors.get(0);
						ValueVector<T> vec2 = currentW.valueVectors.get(1);
						
						//In the case of approximate single objective solvers, current cps can end up
						//dominated by the new vector
						ArrayList<CornerPoint<T>> otherCps  = new ArrayList<CornerPoint<T>>(dim);
						for(CornerPoint<T> c: this.cps){
							if(c.beatenBy(p, this.precision)){
								otherCps.add(c);
							}
						}
						this.cps.removeAll(otherCps);
						
						//Finding the new corner weights is thus easy: combining either one
						// with the new value vector and calculate where they intersect 
						ArrayList<ValueVector<T>> vs1 = new ArrayList<ValueVector<T>>(2);
						ArrayList<ValueVector<T>> vs2 = new ArrayList<ValueVector<T>>(2);
						vs1.add(nvv); vs1.add(vec1);
						vs2.add(nvv); vs2.add(vec2);
						CornerPoint<T> ncp1 = buildCornerPoint(standardW02D, vs1, standardSWI2D);
						ncp1.calcWnE2D(); //this function calculates the intersection in weight
								//space and the maximal possible error at their weight. 
						if(ncp1.maxError>this.epsilon){
							this.cps.add(ncp1);
						}
						CornerPoint<T> ncp2 = buildCornerPoint(standardW02D, vs2, standardSWI2D);
						if(ncp2.maxError>this.epsilon){
							this.cps.add(ncp2);
						}
						
						//Error code: should never occur:
						if(ncp1==null||ncp2==null){System.err.println("NULL corner point!!"); System.exit(5);}
					} else {
						ArrayList<ValueVector<T>> otherVecs = new ArrayList<ValueVector<T>>(currentW.valueVectors);
						ArrayList<Integer> posZeroWeights   = new ArrayList<Integer>(currentW.zeroWeights);
						ArrayList<CornerPoint<T>> otherCps  = new ArrayList<CornerPoint<T>>(dim);
						for(CornerPoint<T> c: this.cps){
							if(c.beatenBy(p, this.precision)){
								otherCps.add(c);
							}
						}
						this.cps.removeAll(otherCps);
						for(int i=0; i<otherCps.size(); i++){
							ArrayList<ValueVector<T>> moreVVs = otherCps.get(i).valueVectors;
							for(int j=0; j<moreVVs.size();j++){
								if(!otherVecs.contains(moreVVs.get(j))){
									otherVecs.add(moreVVs.get(j));
								}
							}
						}
						for(int i=0; i<otherCps.size(); i++){
							ArrayList<Integer> pzs = otherCps.get(i).zeroWeights;
							for(int j=0; j<pzs.size();j++){
								if(!posZeroWeights.contains(pzs.get(j))){
									posZeroWeights.add(pzs.get(j));
								}
							}
						}
						if(DEBUG){
							System.out.println("otherVecs: "+otherVecs.size()+ ", possible 0-weights: "+posZeroWeights.size());
						}	
						
						//Make combo's of n vectors, and dim-n zeroWeights
						boolean[] combo = new boolean[otherVecs.size()];
						for(int i=0; i<otherVecs.size();i++){combo[i]=false;}
						boolean[] comboZ = new boolean[posZeroWeights.size()];
						boolean done=false;
						while(!done){
							int cc = comboCount(combo);
							if(DEBUG) System.out.println(" >"+cc+">"+combo.length);
							if(cc>=1 && cc<=dim-1){
								for(int i=0; i<posZeroWeights.size();i++){comboZ[i]=false;}
								boolean doneZeroWeights=false;
								while((!doneZeroWeights)){
									if(comboAccept(comboZ,(dim-cc-1))){
										//build CPs with these combinators
										int[] swi = new int[cc+1];
										for(int q=0; q<=cc; q++){
											swi[q] = 0;
										}
										CornerPoint<T> cp = buildCornerPoint(comboZ, combo, nvv, posZeroWeights, otherVecs, swi );
										//cp.calcWeightsAndValue();
										
										if(cp.valid){//They're not if no proper solution was found
											//Or if there is a weight that is bigger than 1 or 
											//smaller than zero.
											
											//Check whether CP is not dominated by already present vectors.
											boolean alreadyDominated=false; 
											for(int i=0; ((i<otherVecs.size()) && !alreadyDominated); i++){
												if(cp.beatenBy(otherVecs.get(i).p, precision)){
													alreadyDominated=true;
												}
											}
											if(dim==2){alreadyDominated=false;}
											// And if not, calc CP's max error and add to queue
											if(!alreadyDominated){
												if(this.epsilon==0){
													cp.maxError=1;
													this.cps.add(cp);
												} else  {
													if(currentW.zeroWeights.containsAll(cp.zeroWeights)){
														cp.determineMaxError();
													} else {
														cp.maxError=1;
													}
													if(cp.maxError-this.epsilon>precision){
														this.cps.add(cp);
													}
												}
											}
										}	
									}
									
									int inc=0; 
									while(inc<posZeroWeights.size()){
										if(!comboZ[inc]){
											comboZ[inc]=true;
											inc = posZeroWeights.size()+1;
										} else {
											comboZ[inc] = false;
											inc++;
											if(inc>=posZeroWeights.size()){
												doneZeroWeights = true;
											}
										}
									}
									if(posZeroWeights.size()==0){doneZeroWeights = true;}
								}
							}
							
							//And, increase the combinator:
							int inc=0; 
							while(inc<otherVecs.size()){
								if(!combo[inc]){
									combo[inc]=true;
									inc = otherVecs.size()+1;
								} else {
									combo[inc] = false;
									inc++;
									if(inc>=otherVecs.size()){
										done = true;
									}
								}
							}
						}
						
					}
				}
				
			} else {
				if(DEBUG){
					System.out.println(">> No new Payoff found: "+CentralStatics.vecToString(p.getValue()));
					//System.out.println(">> for cp: \n"+currentW.toString());
				}
			}
			
			if(DEBUG){
				System.out.println("#CornerPoints@iteration: "+this.cps.size());
				for(CornerPoint<T> cp : this.cps){
					System.out.println(cp.toString());
				}
			}
			
			timeout = maxTime < (System.currentTimeMillis()-startTime);
		}
		
		
/*		
////////////////////////////
//////checking max value at belief vector
ArrayList<Double> maxxvall=new ArrayList<Double>();
for(int i=0;i<listmaxlnsupp.size();i++)
{
	
	Double valvb=listmaxlnsupp.get(i).linearScalValue(listmaxlnsupp.get(i).weight);
	maxxvall.add(valvb);
	
}

double maxValue2 = maxxvall.get(0);
for(int j=1;j < maxxvall.size();j++){
if(maxxvall.get(j) > maxValue2){
maxValue2 = maxxvall.get(j);
}
}

for(int i=0;i<maxxvall.size();i++)
{
	if(maxValue2==maxxvall.get(i))
	{   
		System.out.println("###############################################################");
		System.out.println("selected weights :"+listmaxlnsupp.get(i).weight[0]+" "+listmaxlnsupp.get(i).weight[1]);
		System.out.println("selected action    tag :"+listmaxlnsupp.get(i).retrieveTags().get(0));
		System.out.println("selected value    valuevec:"+listmaxlnsupp.get(i).getValue()[0]+" "+listmaxlnsupp.get(i).getValue()[1]);
		System.out.println("###############################################################");
		
		
		
	}
	
}
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
System.out.println("vb scalarized maxValuelsssssss:  "+maxValue2);

System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");

//listmaxlnsupp.clear();
//maxxvall.clear();
	*/	
		
		
		this.readoutTime = (System.currentTimeMillis()-startTime);
		return getPayoffsFromResult();
		
	}
	
	//////////////////////////////////////////////////////////////////////////////
	private  ArrayList<ValueAtBeliefVector<T>> getPayoffsFromResult() {
		ArrayList<ValueAtBeliefVector<T>> result = new ArrayList<ValueAtBeliefVector<T>>(this.vvs.size());
		//System.out.println("payoff list size    "+vvs.size());
		for(ValueVector<T> v : vvs){
			
			//System.out.println("size:  "+v.p.retrieveTags().get(0));
			//listmaxlnsupp.add(v.p);
			result.add(v.p);
		}
		
		return result;
	}

	public ArrayList<CornerPoint<T>> recursiveObtainCornerPoints(boolean[] zeroWeights, ArrayList<ValueVector<T>> vectors, 
				int[] searchWeightsPos, int cnt, double[] maxValsAtExtrema){
		ArrayList<CornerPoint<T>> result = new ArrayList<CornerPoint<T>>(); 
		if(cnt==0){
			zeroWeights = new boolean[dim];
			for(int i=0; i<dim;i++){zeroWeights[i]=true;}
			searchWeightsPos = new int[vectors.size()];
		}
		
		ValueVector<T> vvc = vectors.get(cnt);
		ArrayList<double[]> sws = vvc.getSearchWeights();
		if(cnt<vectors.size()-1){
			for(int i=0; i<sws.size(); i++){
				double[] sw = sws.get(i);
				boolean[] zw = zeroWeights.clone();
				for(int j=0; j<sw.length;j++){
					if(sw[j]>this.precision){//i.e., 1
						zw[j]=false;
					}
				}
				searchWeightsPos[cnt]=i;
				result.addAll(this.recursiveObtainCornerPoints(zw, vectors, searchWeightsPos, cnt+1, maxValsAtExtrema));
			}
			return result;
		} else {
			for(int i=0; i<sws.size(); i++){
				double[] sw = sws.get(i);
				boolean[] zw = zeroWeights.clone();
				for(int j=0; j<sw.length;j++){
					if(sw[j]>this.precision){//i.e., 1
						zw[j]=false;
					}
				}
				searchWeightsPos[cnt]=i;
				CornerPoint<T> cpnew = buildCornerPoint(zw, vectors, searchWeightsPos);
				if(cpnew==null){System.err.println("NULL corner point!"); System.exit(5);}
				cpnew.maxOptimisticAndErrorFromValueAtExtrema(maxValsAtExtrema);
				result.add(cpnew);
			}
			return result;
		}
	}
	
	private CornerPoint<T> buildCornerPoint(boolean[] zcombo, boolean[] vcombo, ValueVector<T> oneVec, ArrayList<Integer> zeroWeights, ArrayList<ValueVector<T>> vectors, int[] swi){
		ArrayList<Integer> nzws = new ArrayList<Integer>(zcombo.length); 
		ArrayList<ValueVector<T>> nvs = new ArrayList<ValueVector<T>>(vcombo.length);
		
		for(int i=0; i<zcombo.length; i++){
			if(zcombo[i]){
				nzws.add(zeroWeights.get(i));
			}
		}
		for(int i=0; i<vcombo.length; i++){
			if(vcombo[i]){
				nvs.add(vectors.get(i));
			}
		}
		nvs.add(oneVec);
		
		return buildCornerPoint(nzws, nvs, swi);
	}
	
	private CornerPoint<T> buildCornerPoint(ArrayList<Integer> zeroWeights, ArrayList<ValueVector<T>> vectors, int[] swi){
		CornerPoint<T> cp = new CornerPoint<T>(vectors, swi, zeroWeights);
		if(optimize2D&&dim==2){
			cp.calcWnE2D();
		} else {
			cp.calcWeightsAndValue();
		}
		return cp;
	}
	
	///////////////////////////////////////////////
	////Imp method for building corner point
	//////////////////////////////////////////////
	
	private CornerPoint<T> buildCornerPoint(boolean[] zeroWeights, ArrayList<ValueVector<T>> vectors, int[] swi){
		ArrayList<Integer> zws = new ArrayList<Integer>(dim);
		for(int i=0; i<zeroWeights.length; i++){
			if(zeroWeights[i]){
				zws.add(new Integer(i));
			}
		}
		CornerPoint<T> cp = new CornerPoint<T>(vectors, swi, zws);
		if(optimize2D&&dim==2){
			cp.calcWnE2D();
		} else {
			cp.calcWeightsAndValue();
		}
		return cp;
	}
}
